home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / prolog / sbprolog / sbp.zoo / sbp_v3.1 / auxil / lzd.c < prev    next >
C/C++ Source or Header  |  1992-02-16  |  7KB  |  257 lines
  1. /*
  2. Lempel-Ziv decompression.  Mostly based on Tom Pfau's assembly language
  3. code.
  4.  
  5. This file is public domain.
  6.  
  7.                                     -- Rahul Dhesi 1991/07/07
  8. */
  9.  
  10. #include "booz.h"
  11. #include <stdio.h>
  12.  
  13. static int push( int ch );
  14. static unsigned rd_dcode( void );
  15. static int init_dtab( void );
  16. static int wr_dchar( int ch );
  17. static int ad_dcode( void );
  18.  
  19. /* must fit in MEM_BLOCK_SIZE */
  20. #define  OUT_BUF_SIZE    4096
  21. #define  IN_BUF_SIZE    4096
  22.  
  23. #define  STACKSIZE   2000
  24. #define  INBUFSIZ    (IN_BUF_SIZE - SPARE)
  25. #define  OUTBUFSIZ   (OUT_BUF_SIZE - SPARE)
  26. #define  MEMERR      2
  27. #define  IOERR       1
  28. #define  MAXBITS     13
  29. #define  CLEAR       256         /* clear code */
  30. #define  Z_EOF       257         /* end of file marker */
  31. #define  FIRST_FREE  258         /* first free code */
  32. #define  MAXMAX      8192        /* max code + 1 */
  33. #define  SPARE       4
  34.  
  35. char out_buf_adr[MEM_BLOCK_SIZE];
  36. #define in_buf_adr   (&out_buf_adr[OUT_BUF_SIZE])
  37.  
  38. struct tabentry {
  39.    unsigned next;
  40.    char z_ch;
  41. };
  42.  
  43. static struct tabentry *table;
  44. static int gotmem = 0;
  45.  
  46. static int init_dtab();
  47. static unsigned rd_dcode();
  48. static int wr_dchar();
  49. static int ad_dcode();
  50.  
  51. static unsigned lzd_sp = 0;
  52. static unsigned lzd_stack[STACKSIZE + SPARE];
  53.  
  54. static int push(int ch)
  55. {
  56.    lzd_stack[lzd_sp++] = ch;
  57.    if (lzd_sp >= STACKSIZE)
  58.       prterror ('f', "Stack overflow in lzd()\n", (char *) 0, (char *) 0);
  59. }
  60.    
  61. #define  pop()    (lzd_stack[--lzd_sp])
  62.  
  63. unsigned cur_code;
  64. unsigned old_code;
  65. unsigned in_code;
  66.  
  67. unsigned free_code;
  68. int nbits;
  69. unsigned max_code;
  70.  
  71. char fin_char;
  72. char k;
  73. unsigned masks[] = { 0, 0, 0, 0, 0, 0, 0, 0, 0,
  74.                         0x1ff, 0x3ff, 0x7ff, 0xfff, 0x1fff };
  75. unsigned bit_offset;
  76. unsigned output_offset;
  77. static FILE *in_file;
  78. static FILE *out_file; 
  79.  
  80. #ifdef TEXT_MODE
  81. int first;
  82. extern int text_mode;
  83. char *_fname;
  84. #endif
  85.  
  86. int lzd(FILE *input_file, FILE *output_file, char *fname)
  87. /* input & output file handles */
  88. {
  89. #ifdef TEXT_MODE
  90.    first=1;
  91.    _fname=fname;
  92. #endif
  93.    in_file = input_file;                 /* make it avail to other fns */
  94.    out_file = output_file;               /* ditto */
  95.    nbits = 9;
  96.    max_code = 512;
  97.    free_code = FIRST_FREE;
  98.    lzd_sp = 0;
  99.    bit_offset = 0;
  100.    output_offset = 0;
  101.  
  102.    if (gotmem == 0) {
  103.       table = (struct tabentry *) 
  104.          malloc (MAXMAX * sizeof (struct tabentry) + SPARE);
  105.       gotmem++;
  106.    }
  107.    if (table == (struct tabentry *) 0)
  108.       memerr();
  109.  
  110.    fread(in_buf_adr, 1, INBUFSIZ, in_file);
  111.    if (ferror(in_file))
  112.       return(IOERR);
  113.  
  114.    init_dtab();             /* initialize table */
  115.  
  116. loop:
  117.    cur_code = rd_dcode();
  118.    if (cur_code == Z_EOF) {
  119.       if (output_offset != 0) {
  120.                  if (out_file != NULL) {
  121. #ifdef TEXT_MODE
  122.      if( text_mode ) {
  123.             if( first && output_file && output_offset>=4 && to_long(out_buf_adr)!=0x03131211 ) {
  124.                 freopen(fname,"w",output_file);
  125.          }
  126.          first=0;
  127.      }
  128. #endif
  129.  
  130.        if (fwrite(out_buf_adr, 1, output_offset, out_file) != output_offset)
  131.                             prterror ('f', "Output error in lzd()\n",
  132.                         (char *) 0, (char *) 0);
  133.          }
  134.          addbfcrc(out_buf_adr, output_offset);
  135.       }
  136.       return (0);
  137.    }
  138.  
  139.    if (cur_code == CLEAR) {
  140.       init_dtab();
  141.       fin_char = k = old_code = cur_code = rd_dcode();
  142.       wr_dchar((int) k);
  143.       goto loop;
  144.    }
  145.  
  146.    in_code = cur_code;
  147.    if (cur_code >= free_code) {        /* if code not in table (k<w>k<w>k) */
  148.       cur_code = old_code;             /* previous code becomes current */
  149.       push(fin_char);
  150.    }
  151.  
  152.    while (cur_code > 255) {               /* if code, not character */
  153.       push(table[cur_code].z_ch);         /* push suffix char */
  154.       cur_code = table[cur_code].next;    /* <w> := <w>.code */
  155.    }
  156.  
  157.    k = fin_char = cur_code;
  158.    push(k);
  159.    while (lzd_sp != 0) {
  160.       wr_dchar((int) pop());
  161.    }
  162.    ad_dcode();
  163.    old_code = in_code;
  164.  
  165.    goto loop;
  166. } /* lzd() */
  167.  
  168. /* rd_dcode() reads a code from the input (compressed) file and returns
  169. its value. */
  170. static unsigned rd_dcode(void)
  171. {
  172.    register char *ptra, *ptrb;    /* miscellaneous pointers */
  173.    unsigned word;                     /* first 16 bits in buffer */
  174.    unsigned byte_offset;
  175.    char nextch;                           /* next 8 bits in buffer */
  176.    unsigned ofs_inbyte;               /* offset within byte */
  177.  
  178.    ofs_inbyte = bit_offset % 8;
  179.    byte_offset = bit_offset / 8;
  180.    bit_offset = bit_offset + nbits;
  181.  
  182.    if (byte_offset >= INBUFSIZ - 5) {
  183.       int space_left;
  184.  
  185.       bit_offset = ofs_inbyte + nbits;
  186.       space_left = INBUFSIZ - byte_offset;
  187.       ptrb = byte_offset + in_buf_adr;          /* point to char */
  188.       ptra = in_buf_adr;
  189.       /* we now move the remaining characters down buffer beginning */
  190.       while (space_left > 0) {
  191.          *ptra++ = *ptrb++;
  192.          space_left--;
  193.       }
  194.       fread(ptra, 1, byte_offset, in_file);
  195.       if (ferror(in_file))
  196.          prterror ('f', "Input error in lzd:rd_dcode\n", 
  197.                 (char *) 0, (char *) 0);
  198.       byte_offset = 0;
  199.    }
  200.    ptra = byte_offset + in_buf_adr;
  201.    /* NOTE:  "word = *((int *) ptra)" would not be independent of byte order. */
  202.    word = (unsigned char) *ptra; ptra++;
  203.    word = word | ((unsigned char) *ptra) << 8; ptra++;
  204.  
  205.    nextch = *ptra;
  206.    if (ofs_inbyte != 0) {
  207.       /* shift nextch right by ofs_inbyte bits */
  208.       /* and shift those bits right into word; */
  209.       word = (word >> ofs_inbyte) | (((unsigned)nextch) << (16-ofs_inbyte));
  210.    }
  211.    return (word & masks[nbits]); 
  212. } /* rd_dcode() */
  213.  
  214. static int init_dtab(void)
  215. {
  216.    nbits = 9;
  217.    max_code = 512;
  218.    free_code = FIRST_FREE;
  219. }
  220.  
  221. static int wr_dchar (int ch)
  222. {
  223.    if (output_offset >= OUTBUFSIZ) {      /* if buffer full */
  224.       if (out_file != NULL) {
  225. #ifdef TEXT_MODE
  226.      if( text_mode ) {
  227.             if( first && out_file && output_offset>=4 && to_long(out_buf_adr)!=0x03131211 ) {
  228.                 freopen(_fname,"w",out_file);
  229.          }
  230.          first=0;
  231.      }
  232. #endif
  233.  
  234.          if (fwrite(out_buf_adr, 1, output_offset, out_file) != output_offset)
  235.             prterror ('f', "Write error in lzd:wr_dchar\n", 
  236.                     (char *) 0, (char *) 0);
  237.       }
  238.       addbfcrc(out_buf_adr, output_offset);     /* update CRC */
  239.       output_offset = 0;                  /* restore empty buffer */
  240.    }
  241.    out_buf_adr[output_offset++] = ch;        /* store character */
  242. } /* wr_dchar() */
  243.  
  244. /* adds a code to table */
  245. static int ad_dcode(void)
  246. {
  247.    table[free_code].z_ch = k;                /* save suffix char */
  248.    table[free_code].next = old_code;         /* save prefix code */
  249.    free_code++;
  250.    if (free_code >= max_code) {
  251.       if (nbits < MAXBITS) {
  252.          nbits++;
  253.          max_code = max_code << 1;        /* double max_code */
  254.       }
  255.    }
  256. }
  257.